use std::{i32::MAX, collections::HashMap};

#[test]
fn test_coin_change() {
    // println!("{}", coin_change(vec![1,2,5], 11));
    println!("{}", coin_change(vec![2], 3));
}

// 322
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    // let mut minCount = MAX;
    // bfs(&coins, amount, 0, &mut minCount); // timeout
    // return minCount;

    // let mut memo: HashMap<i32, i32> = HashMap::new();
    // return bfs_memo(&coins, amount, &mut memo);  // timeout at 31 / 189

    let mut dp: Vec<i32> = vec![0; amount as usize + 1];
    for a in 1..=amount {
        let mut min_count = MAX;
        for c in coins.iter() {
            if a - c >= 0 {
                if dp[(a-c) as usize] != -1 {
                    min_count = min_count.min(dp[(a-c) as usize]);
                }
            }
        }
        if min_count != MAX {
            dp[a as usize] = min_count + 1;
        } else {
            dp[a as usize] = -1;
        }
        println!("{}", dp[a as usize]);
    }
    dp[amount as usize]
}

// 返回需要的最少硬币数
fn bfs_memo(coins: &Vec<i32>, amount: i32, memo: &mut HashMap<i32, i32>) -> i32 {
    if amount == 0 {
        return 0;
    }
    if amount < 0 {
        return -1;
    }
    if let Some(c) = memo.get(&amount) {
        return *c;
    }
    let mut min_count = MAX;
    for c in coins {
        let count = bfs_memo(coins, amount - c, memo);
        if count != -1 && count < min_count {
            min_count = count + 1;
        }
    }
    if min_count == MAX {
        return -1;
    }
    memo.insert(amount, min_count);
    return min_count;
}

fn bfs(coins: &Vec<i32>, amount: i32, count: i32, minCount: &mut i32) {
    if amount == 0 {
        if count < *minCount {
            *minCount = count;
        }
        return;
    }
    if amount < 0 {
        return;
    }
    if count > *minCount {
        return;
    }
    for v in coins {
        bfs(coins, amount - v, count + 1, minCount);
    }
}